package LeetCode.month01.day27;

import java.util.ArrayList;
import java.util.List;

public class No567 {
    public static void main(String[] args) {
        System.out.println(checkInclusion("ab","ba"));
    }

    public static boolean checkInclusion(String s1, String s2) {
        if(s2.contains(s1)) return true;
        int[] arr = new int[26];
        char[] chars1 = s1.toCharArray();
        int less = 0;
        int n = chars1.length;
        for (int i = 0; i < n; i++) {
            int index = chars1[i]-'a';
            if(arr[index]==0) less++;
            arr[index]++;
        }
        char[] chars2 = s2.toCharArray();
        for (int i = 0; i < s2.length(); i++) {
            int index = chars2[i]-'a';
            arr[index]--;
            if(arr[index]==0) less--;
            if(i<n-1) continue;
            if(less==0) return true;
            int out = chars2[i-n+1]-'a';
            if(arr[out]==0) less++;
            arr[out]++;
        }
        return false;
    }

    public static boolean checkInclusion1(String s1, String s2) {
        if(s2.contains(s1)) return true;
        int n =s1.length();
        char[] chars = s1.toCharArray();
        List<String> list = new ArrayList<>();
        boolean[] visit = new boolean[n];
        dfs(list,0,visit,chars,new StringBuilder());
        System.out.println(list);
        for (String s : list) {
            if(s2.contains(s)) return true;
        }
        return false;
    }

    public static void dfs(List<String> list,int index,boolean[] visit,char[] chars,StringBuilder sb){
        if(index==chars.length) {
            list.add(sb.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if(!visit[i]){
                sb.append(chars[i]);
                visit[i]=true;
                dfs(list,index+1,visit,chars,sb);
                sb.deleteCharAt(sb.length()-1);
                visit[i]=false;
            }
        }
    }
}
